package com.zklh.leetcode.top100;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 单词拆分算法实现
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/12/14
 */
public class Solution139 {

    /**
     * s = "applepenapple", wordDict = ["apple", "pen"]
     * "leetcode", wordDict = ["leet", "code"]
     *  s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
     * @param s
     * @param wordDict
     * @return
     */
    private Map<String, Boolean> sToResult = new HashMap<>();
    public boolean wordBreak(String s, List<String> wordDict) {
        if (sToResult.containsKey(s)) {
            return sToResult.get(s);
        }
        if ("".equals(s)) {
            sToResult.put("", true);
            return true;
        }
        for (String word : wordDict) {
            if (s.length() >= word.length() && word.equals(s.substring(0, word.length())) && wordBreak(s.substring(word.length()),wordDict)) {
                return true;
            }
        }
        sToResult.put(s, false);
        return false;
    }

    public static void main(String[] args) {
        Solution139 solution = new Solution139();
        System.out.println(solution.wordBreak("leetcode", Arrays.asList("leet", "code")));
        System.out.println(solution.wordBreak("applepenapple", Arrays.asList("apple", "pen")));
        System.out.println(solution.wordBreak("catsandog", Arrays.asList("cats", "dog", "sand", "and", "cat")));
        System.out.println(solution.wordBreak("cars", Arrays.asList("car","ca","rs")));
    }
}